This invention relates to the fields of mesh representations of object surfaces and volumetric representations of object volumes, and, more specifically, to deriving a mesh representation of a surface from a volumetric representation of an object.
Volumetric representations of objects are generated in many applications, such as medical imaging and laser scanning. In these applications, a volume of a three dimensional object is typically represented by data in the form of volume elements (xe2x80x98voxelsxe2x80x99), each associated with a point in space and a value known as an iso-value representative of a characteristic or quality of the object at the point in space. For example, in magnetic resonance imaging, a volumetric representation of at least a portion of the human body is formed, comprising a plurality of voxels, in which the iso-value associated with each voxel is the intensity of the image at the point in space corresponding to the image.
It is often desirable to be able to extract from the volumetric representation a representation of a particular surface within the volume represented by the volumetric representation. For example, in the field of magnetic resonance imaging, a physician may want to extract and display a surface representation of a selected organ, such as the brain or the heart, from a volumetric representation of the upper torso and head of a human body. Moreover, a mesh representation, i.e., a representation in which an object surface is represented by a plurality of tessellated polygons such as triangles, is often a convenient form for representing object surfaces because it can be easily refined to more detailed levels of resolution in a hierarchical fashion depending on the application involved. The hierarchical arrangement facilitates applications involving progressive resolution, such as Web applications in which it is desired to rapidly display a coarse representation of object which is the progressively filled in at higher levels of resolution.
A so-called xe2x80x98Marching Cubesxe2x80x99 algorithm, described in W. E. Lorenson and H. E. Cline, xe2x80x9cMarching Cubes: A High Resolution 3D Surface Construction Algorithm,xe2x80x9d Computer Graphics(Proceedings SIGGRAPH ""87), 21(4), 163-169, July 1987, is presently available for extracting a meshed triangle representation from a volumetric representation. However, the triangular representation formed by this method often represents an object surface with an excessive number of triangles, and also with triangles with bad aspect ratios, i.e., aspect ratios which are likely to lead to loss of precision. Mesh representations utilizing an excessive number of triangles lead to inefficiency because they require more time to display and more resources to store. Moreover, mesh representations utilizing triangles with bad aspect ratios are disfavored because they can cause instability problems in down stream applications such as finite element simulation.
The invention provides a method of extracting a mesh representation of a surface from a volumetric representation of at least a portion of an object. A surface is derived from the volumetric representation. Then, a seed point on the surface is selected and, subject to any applicable constraints, the neighborhood of the point is grown to cover a portion of the surface. If any constraints are applicable and encountered during this process, the growth is halted, and the size of the neighborhood reduced by a specified amount. If any portions of the surface remain uncovered, the process iterates by selecting additional seed points, and growing additional neighborhoods in like manner to the process described, until the surface is substantially completely covered. Polygons are then formed by selectively connecting seed points with connectors. These polygons form a mesh representation of the surface. In one implementation, the polygons are formed using a surface Delaunay triangulation algorithm.
Other systems, methods, data structures, features and advantages of the invention will be or will become apparent to one with skill in the art upon examination of the following figures and detailed description. It is intended that all such additional systems, methods, features and advantages be included within this description, be within the scope of the invention, and be protected by the accompanying claims.